package com.yin.algorithms;

import com.yin.Sort;

public class MergeSort implements Sort {

    /*
    *   归纳:
    *   分治 -> 合并
    *   先把数组递归分成很多个单一有序的数组，最后从下往上合并在一块
    *   left, right, mid都只讨论数组下标，不代表数组内的第几个元素
    *   在不同次递归里left, right, mid的含义都会发生变化
    *
    *   left -> 左数组第一个元素下标, 未分割前的数组第一个元素下标
    *   mid -> 左数组最后一个元素下标
    *   (mid + 1) -> 右数组第一个元素下标
    *   right -> 右数组最后一个元素下标, 未分割前的数组最后一个元素下标
    * */

    @Override
    public void sort(int[] arr) {

        //申请一个与原数组等长的临时数组用于合并
        //该数组的元素会被一块一块填充直到排序完成，所以不会从0开始填充该数组
        int[] temp = new int[arr.length];

        //因为arr数组第一个元素下标为0，所以最后一个元素的下标为(arr.length - 1)
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    //  [left, right)
    //left -> 数组第一个元素下标
    //right -> 数组最后一个元素下标
    //因为左数组不包括right的位置，所以right数组的起始位置为(mid + 1)
    private void mergeSort(int[] arr, int[] temp, int left, int right) {

        //如果数组已有序则返回到上一层递归merge(condition: left >= right, left = right -> 数组)
        //因为想要merge必须有两个同是有序的数组，所以不必执行merge，因为一个数组merge不了
        if(left >= right) {
            return;
        }

        //如果数组仍不是有序则分割数组

        //中间点
        //mid还是左边数组最后一个元素的下标
        // >>1 = /2
        int mid = (left + right) >> 1;

        //对左数组继续进行归并
        //left - mid
        //left -> 左数组第一个元素下标
        //mid -> 左数组最后一个元素下标
        mergeSort(arr, temp, left, mid);

        //对右数组继续进行归并
        //(mid + 1) - right
        //(mid + 1) -> 右数组第一个元素下标
        //right -> 右数组最后一个元素下标
        mergeSort(arr, temp, mid + 1, right);

        //合并，只有等上面的递归返回完了才会进行合并，所以合并实质上是从下往上合并的
        merge(arr, temp, left, mid, right);
    }

    //对两个已有序的数组进行合并并同步到原数组
    /*
    *
    *   left, right都是arr数组里面的下标，所以merge中放到temp数组的值的下标并不是从0开始，对应的一段数组只会放回原数组中对应的位置，所以这也就是为什么
    *       从sort方法就要创建一个唯一的temp数组而不是每次递归创建一个然后从0下标开始填充数据
    * */
    private void merge(int[] arr, int[] temp, int left, int mid, int right) {

        //左数组第一个未排序的元素下标
        int i = left;

        //右数组第一个未排序的元素下标
        int j = mid + 1;

        //临时数组元素的下标
        int k = left;

        while(i <= mid && j <= right) {

            //如果左边数组的i位置的值小则放到temp的k下标
            if(arr[i] < arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }

        //如果左或右数组还有剩余则直接合并，因为数组本身就有序所以可以直接合并不必排序
        //合并左数组剩余
        while(i <= mid)
            temp[k++] = arr[i++];

        //合并右数组剩余
        while(j <= right)
            temp[k++] = arr[j++];

        //同步到原数组
        while(left <= right) {

            //此时的left为两个被分割数组合并后在原数组的位置
            //left - right就是一个原数组中已归并排序完的已有序的数组，在原数组的哪里分割的就在哪里填充上去
            //所以不会从0开始, arr[0] = temp[0]是错误的
            arr[left] = temp[left];
            left++;
        }
    }
}
